package com.zhupf.part3;

import java.util.*;

/**
 * @author zhupf
 * @date 2023年10月27日 9:29
 * @Description
 *
 * 找到字符串中所有字母异位词
 *
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 *
 *
 */
public class FindAnagrams {

    public static void main(String[] args) {

        String s = "vwwvv";
        String p = "vwv";
        System.out.println(findAnagrams(s, p));

    }

    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        char[] array = p.toCharArray();

        Map<Character,Integer> targetMap = new HashMap<>();
        Map<Character,Integer> tmpMap = new HashMap<>();
        for (char c : array) {
            targetMap.put(c,(targetMap.get(c) == null ? 1 : targetMap.get(c)+1));
        }
        int l =0 , r = 0;
        int length = chars.length;
        int tmpSize = 0;
        while (r<length){
            if(targetMap.containsKey(chars[r])){
                while (tmpMap.containsKey(chars[r]) && tmpMap.get(chars[r]).equals(targetMap.get(chars[r]))){
                    tmpMap.put(chars[l],tmpMap.get(chars[l])-1);
                    l ++ ;
                    tmpSize --;
                }
                tmpMap.put(chars[r],tmpMap.get(chars[r]) == null ? 1 : tmpMap.get(chars[r])+1);
                r++;
                tmpSize ++;
                if(tmpSize == array.length){
                    list.add(l);
                    tmpMap.put(chars[l],tmpMap.get(chars[l])-1);
                    tmpSize -- ;
                    l++;
                }
            }else {
                l = ++ r;
                tmpMap.clear();
                tmpSize = 0;
            }
        }
        return list;
    }

}
